template<typename T, typename CombineFunc>
class SparseTable {
public:
    SparseTable() = default;
    
    explicit SparseTable(const std::vector<T>& data, CombineFunc func)
        : combine_func(std::move(func)) 
    {
        Initialize(data);
    }

    // 禁止拷贝和赋值
    SparseTable(const SparseTable&) = delete;
    SparseTable& operator=(const SparseTable&) = delete;

    void Initialize(const std::vector<T>& data) {
        assert(!data.empty());
        const size_t n = data.size();
        
        
        log_table.resize(n + 1);
        log_table[0] = 0;
        for (size_t i = 1; i <= n; ++i) {
            log_table[i] = log_table[i / 2] + 1;
        }

        const int max_power = log_table[n] + 1;
        st_table.resize(n, std::vector<T>(max_power));
        

        for (size_t i = 0; i < n; ++i) {
            st_table[i][0] = data[i];
        }

        for (int j = 1; (1U << j) <= n; ++j) {
            for (size_t i = 0; i + (1 << j) <= n; ++i) {
                st_table[i][j] = combine_func(
                    st_table[i][j - 1],
                    st_table[i + (1 << (j - 1))][j - 1]
                );
            }
        }
    }

    T Query(size_t left, size_t right) const {
        assert(left <= right);
        assert(right < st_table.size());
        
        const int k = log_table[right - left + 1] - 1;
        return combine_func_(
            st_table[left][k],
            st_table[right - (1 << k) + 1][k]
        );
    }

private:
    std::vector<int> log_table;
    std::vector<std::vector<T>> st_table;
    CombineFunc combine_func;

    static int CalculateLog(int n) {
        return std::bit_width(static_cast<unsigned>(n)) - 1;
    }
};

namespace functional {
    template<typename T>
    struct GcdCombiner {
        T operator()(T a, T b) const {
            while (b != 0) {
                T temp = b;
                b = a % b;
                a = temp;
            }
            return a;
        }
    };

    template<typename T>
    struct LcmCombiner {
        T operator()(T a, T b) const {
            return a / gcd_(a, b) * b;
        }
    private:
        GcdCombiner<T> gcd_;
    };

    template<typename T>
    struct BitAndWrapper {
        T operator()(T a, T b) const noexcept {
            return a & b;
        }
    };

    template<typename T>
    struct BitOrWrapper {
        T operator()(T a, T b) const noexcept {
            return a | b;
        }
    };
} // namespace functional


template<typename T>
using RangeMinQuery = SparseTable<T, std::less<T>>;

template<typename T>
using RangeMaxQuery = SparseTable<T, std::greater<T>>;

template<typename T>
using RangeGcdQuery = SparseTable<T, functional::GcdCombiner<T>>;

template<typename T>
using RangeLcmQuery = SparseTable<T, functional::LcmCombiner<T>>;

template<typename T>
using RangeBitAndQuery = SparseTable<T, functional::BitAndWrapper<T>>;

template<typename T>
using RangeBitOrQuery = SparseTable<T, functional::BitOrWrapper<T>>;
